'''
https://leetcode.cn/problems/count-number-of-bad-pairs
'''
from collections import defaultdict
from typing import List


class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)
        good_pairs = 0
        # good pair: j > i and j - i == nums[j] - nums[i]
        #                       => i - nums[i] = j - nums[j]
        dic = defaultdict(int)
        for i in range(n):
            v = i - nums[i]
            if v in dic:
                good_pairs += dic[v]
            dic[v] += 1

        # n-1 + n-2 + ... + 1
        n_total = int((n-1+1)/2*(n-1))
        return n_total - good_pairs
